package Z代码随想录.数组;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

// 水果成篮
// 本题也是数组题
// 本题的意思是在数组中找到连续的最长的子序列，并且子序列中只能包含两种元素，并返回子序列的长度
// 我们有两个篮子，来存放 数组中的元素，目的是从左到右，遍历数组中的元素
// 如果遍历到的是两种元素，就边遍历并记录长度，当出现第三个不同元素的时候，就停止
public class Leetcode904 {

    // 暴力枚举
    // 从头开始遍历，两层循环，外层控制起始位置，内层控制结束位置，当碰到第三个不一样的元素时候，就记录子序列长度，重新开始新的起始位置
    // 这种做法时间复杂度达到O(n^2)，超出了时间限制
    public static int totalFruit1(int[] fruits) {
        int i = 0;
        int j = 0;
        int ans = 0;
        int subLength = 0;
        for (i = 0; i < fruits.length; i++) {
            HashSet<Integer> hashSet = new HashSet<>();
            for (j = i; j < fruits.length; j++) {
                // 将数组元素依次遍历放入到 hashset 中
                hashSet.add(fruits[j]);
                // 由于 set 会去重，如果 set.size 大于 2 ，说明出现了第三个元素，就停止
                if (hashSet.size() > 2) {
                    subLength = j - i;  // 记录子序列的长度
                    ans = Math.max(ans, subLength); // 与 ans进行比较，如果比ans大，就更新，并退出当前循环
                    break;
                }
                // 此处还要考虑如果元素中 种类只有两种情况下，一开始没有考虑到！
                subLength = j - i + 1;
                ans = Math.max(subLength, ans);
            }
        }
        return ans;
    }

    // 可以采用滑动窗口思想，来解决这道题，时间复杂为O(n)
    // 利用哈希表 key来记录元素，value来记录出现次数，定义一个 right 指针依次遍历
    // 在没有出现第三种元素的时候，随时更新 子序列的长度
    // 当出现第三种元素时候，就开始进行 更新left的值
    // 当前两种元素当成任意一个 value 值为0的时候 , 开始 right 指针往后查找 第三个种类的元素，找到后又停止
    // 上述动作反复循环
    public static int totalFruit(int[] fruits) {
        int left = 0;
        int right = 0;
        int ans = 0;
        int subLength = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (right = 0; right < fruits.length; right++) {
            // 在哈希表中依次放入数组中元素，并且记录元素出现次数
            hashMap.put(fruits[right], hashMap.getOrDefault(fruits[right], 0) + 1);


            // 当哈希表中长度超过2的时候说明，第三种元素出现了
            while (hashMap.size() > 2) {
                // left 从左往后，开始删除元素       hashMap.put(fruits[left], hashMap.get(fruits[left] -1)，一开始写错了
                hashMap.put(fruits[left], hashMap.get(fruits[left]) - 1);
                // 直到找到第一个次数删成0的元素
                if (hashMap.get(fruits[left]) == 0) {
                    hashMap.remove(fruits[left]);
                }
                // 如果哈希表中两个元素都没有删成0次，就继续往后left
                left++;
            }
            // 此处记录当元素没有出现第三种类的 子序列长度
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] fruits1 = new int[]{1, 2, 1};
        int[] fruits2 = new int[]{0, 1, 2, 2};
        int[] fruits3 = new int[]{1, 2, 3, 2, 2};
        int[] fruits4 = new int[]{3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};

        System.out.println(totalFruit(fruits1));
        System.out.println(totalFruit(fruits2));
        System.out.println(totalFruit(fruits3));
        System.out.println(totalFruit(fruits4));
    }
}
